/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
    struct cmp
    {
        bool operator()(const ListNode* l1, const ListNode* l2)
        {
            return l1->val > l2->val;
        }
    };
 
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        priority_queue<ListNode*, vector<ListNode*>, cmp> heap;
 
        for(auto& e : lists) // 所有头结点进入小根堆
        {
            if(e)
                heap.push(e);
        }
        ListNode* newHead = new ListNode(0);
        ListNode* tmp = newHead;
        while(!heap.empty())
        {   // 尾插堆顶结点到新链表，再把旧链表下个结点插入小根堆
            ListNode* cur = heap.top();
            heap.pop();
            tmp->next = cur;
            tmp = cur;
            if(cur->next)
            {
                heap.push(cur->next);
            }
        }
        tmp = newHead->next;
        delete newHead;
        return tmp;
    }
};